# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.last_node = None
        self.max_node = None
        self.min_node = None

        def func(node):
            if node.left:
                func(node.left)

            if self.last_node and self.last_node.val > node.val:
                self.max_node = self.max_node if self.max_node and self.max_node.val > self.last_node.val else self.last_node
                self.min_node = node
            if self.min_node:
                self.min_node = self.min_node if self.min_node.val < node.val else node
            self.last_node = node

            if node.right:
                func(node.right)

        func(root)
        min_node_val = self.min_node.val
        self.min_node.val = self.max_node.val
        self.max_node.val = min_node_val
